/*
 * @lc app=leetcode.cn id=664 lang=typescript
 *
 * [664] 奇怪的打印机
 */

// @lc code=start
function strangePrinter(s: string): number {
  let size = s.length;
  const dp = new Array(size).fill(0).map(() => new Array(size).fill(0));

  for (let i = size - 1; i >= 0; i--) {
    // 边界，长度为1的字符最多打印1次
    dp[i][i] = 1;
    for (let j = i + 1; j < size; j++) {
      if (s[i] === s[j]) {
        dp[i][j] = dp[i][j - 1];
      } else {
        let min = Number.POSITIVE_INFINITY;
        for (let k = i; k < j; k++) {
          min = Math.min(min, dp[i][k] + dp[k + 1][j]);
        }
        dp[i][j] = min;
      }
    }
  }

  return dp[0][size - 1];
}
// @lc code=end
